1. Field of the Invention
The present invention relates to methods and apparatus for data compression and decompression, and particularly although not exclusively to such methods and apparatus for compression and decompression of still or video images and/or audio data.
2. Description of Related Art
There are number of known approaches to compressing image and audio data. Examples include the well known Joint Picture Expert Group (JPEG) algorithm for still picture encoding and decoding, and the Moving Picture Expert Group (MPEG) algorithms for encoding and decoding video data. These, together with many other encoding and decoding systems, make use of spatial transforms such as the Discrete Cosine Transform (DCT) to convert the original image data into a compressed form. Other algorithms use alternative transforms such as the Wavelet Transform.
Typically, the output from the chosen transform is a series of transform coefficients which, taken as a whole, define the encoded compressed form of the original data. When the compressed data needs to be transferred across a communications medium such as for example the Internet or a low-bandwidth wireless connection, the coefficients are converted into binary form (bits) which can then be transmitted according to any preferred communications protocol.
In an “embedded” system (using an “embedded quantizer”), the transform coefficients are ordered into layers of significance (bit planes), with the most significant bits normally being transmitted first. With such an “embedded” coding scheme, the recipient initially receives a low-resolution image which as transmission progresses is gradually refined into a higher-resolution image. That gives the recipient the possibility of terminating the transmission at any time once the image that has been received is of sufficient resolution for the recipient's needs.
Most embedded systems make use of the concept of significance-switching, in other words they provide some mechanism for advising the decoder of the position of the most significant bit of each of the coefficients. Without significance-switching, a considerable amount of the available bandwidth would be wasted by repeatedly sending insignificant bits for coefficients in which the first significant bit has not yet been reached. For positive coefficients, this means repeatedly sending zeros when the first significant bit (ie a 1) has not yet been reached. Some systems such as that by Shapiro do this by scanning one bit plane at a time: see Shapiro, IEEE Transactions on Signal Processing, 41(12); 3445 to 3462 December 1993 (further described in U.S. Pat. No. 5,321,776 and U.S. Pat. No. 5,315,670). Others notify the decoder of the most significant bit position by sending it explicitly. Several systems such as those described in documents WO 99/08449 and WO 98/37700 make use of masking techniques to improve bit transmission efficiency.
With all of the above techniques, the most significant bit of each individual coefficient is sent first, followed by successively less significant bits, bit plane by bit pane. When a particular cut-off bit plane is reached, the system considers that no further refinement of the coefficient would be worthwhile, and hence no further bits which may exist below the cut-off bit plane are sent.